package com.example;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Stack;

public class App {

    public static int n; // 顶点数
    public static int count;
    public static int[] DFN;
    public static int[] low;
    public static boolean[] inStack;
    public static int group;
    public static int [] belong;
    public static Stack<Integer> stack;
    public static ArrayList<edge> [] map;
    public static ArrayList<String> result = new ArrayList<>();

    static  class edge{
        public int a; // 边的起点
        public int b; // 边的终点
        public edge(int a, int b){
            this.a = a;
            this.b = b;
        }
    }

    public void init(){
        count = 1;
        DFN = new int[n + 1];
        low = new int[n + 1];
        inStack = new boolean[n + 1];
        group = 0;
        belong = new int [n + 1];
        stack = new Stack<>();
        map = new ArrayList[n + 1];
        for(int i=1; i<=n; i++){
            DFN[i] = -1;
            low[i] = -1;
            inStack[i] = false;
            belong[i] = -1;
            map[i] = new ArrayList<>();
        }
    }

    public void tarJan(int start){
        DFN[start] = count ++;
        low[start] = DFN[start];
        inStack[start] = true;
        stack.push(start);
        int j = start;
        for(int i = 0;i < map[start].size();i++) {
            j = map[start].get(i).b;
            if(DFN[j] == -1) {
                tarJan(j);
                low[start] = Math.min(low[start], low[j]);
            } else if(inStack[j]) {
                low[start] = Math.min(low[start], DFN[j]);
            }
        }
        if(DFN[start] == low[start]) {
            group++;
            do {
                j = stack.pop();
                belong[j] = group;
                inStack[j] = false;
            } while(j != start);
        }
    }

    public boolean topSort(ArrayList<edge>[] lessMap, int[] degree) {
        int count = 0;
        Stack<Integer> s = new Stack<Integer>();
        for(int i = 1;i < degree.length;i++) {
            if(degree[i] == 0) {
                count++;
                s.push(i);
            }
        }
        if(count > 1)
            return false;
        while(!s.empty()) {
            int start = s.pop();
            count = 0;
            for(int i = 0;i < lessMap[start].size();i++) {
                int j = lessMap[start].get(i).b;
                degree[j]--;
                if(degree[j] == 0) {
                    count++;
                    s.push(j);
                }
            }
            if(count > 1)
                return false;
        }
        return true;
    }


    public void getResult() {
        for(int i = 1;i <= n;i++) {
            if(DFN[i] == -1)
                tarJan(i);
        }
        ArrayList<edge>[] lessMap = new ArrayList[group + 1];
        int[] degree = new int[group + 1];
        for(int i = 1;i <= group;i++)
            lessMap[i] = new ArrayList<edge>();
        for(int i = 1;i < map.length;i++) {
            for(int j = 0;j < map[i].size();j++) {
                int a = map[i].get(j).a;
                int b = map[i].get(j).b;
                if(belong[a] != belong [b]) {
                    lessMap[belong[a]].add(new edge(belong[a], belong[b]));
                    degree[belong[b]]++;
                }
            }
        }
        if(topSort(lessMap, degree)) {
            result.add("这是欧拉环");
        } else {
            result.add("这不是欧拉环");
        }
        return;
    }

    public static void main(String[] args) {
        System.out.println("Euler Circuit...");

        App test = new App();
        Scanner in = new Scanner(System.in);
        System.out.println("请输入定点数和边数,以空格分开:");

        n = in.nextInt();
        int k = in.nextInt();

        System.out.println("顶点数：" + n + ", 边数：" + k);
        test.init();

        for(int i = 0;i < k;i++) {
            System.out.println("请输入第" + (i+1) + "条边的坐标, 以空格分开：");
            int a = in.nextInt();
            int b = in.nextInt();
            map[a].add(new edge(a, b));
        }
        test.getResult();

        for(int i = 0;i < result.size();i++) {
            System.out.println(result.get(i));
        }
    }
}
